퀵정렬

피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법.

값을 서로 교체하는데에 N번, 엇갈린 경우 교체 이후에 우너소가 반으로 나누어지므로,

전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로 평균적으로 O(NlonN)의 시간 복잡도를 가진다.

원소를 절반씩 나눌 때 log N의 시간 복잡도가 나오는 대표적인 예시는 완전 이진 트리이다.

이런한 완전 이진 트리 형태는 흔히 컴퓨터 공학에서 가장 선호하는 이상적인 형태이다.

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<stdlib.h>

#define SIZE 100

int a[SIZE];

int swap(int *a, int *b){

int temp=*a;

*a=*b;

*b=temp;

}

void quickSort(int start, int end){

if(start>=end)return;

int key=start, i=start+1, j=end, temp;

while(i<=j){

while(i<=end && a[i]<=a[key])i++;

while(j>start && a[j]>=a[key])j--;

if(i>j)swap(&a[key],&a[i]);

else swap(&a[i], &a[j]);

}

quickSort(start,j-1);

quickSort(j+1,end);

}

int main(void){

int n;

scanf("%d",&n);

for(int i=0;i<n;i++) scanf("%d", &a[i]);

quickSort(0,n-1);

for(int i=0;i<n;i++){

printf("%d", a[i]);

}

system("pause");

return 0;

}

편향된 분할이 발생할 때, 연산의 양이 O(N^2)이다. 따라서 실제로 정렬을 함에 있어서는 퀵 정렬을 직접 구현하지 않는다.

C++의 Algorithm라이브러리의 sort()함수는 퀵정렬을 기반으로 하되 O(NlogN)을 보장한다.

Quick sort